package com.zhang.二叉树;

import com.zhang.printer.BinaryTreeInfo;

import java.util.Comparator;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 张吉鑫
 * @Description 二叉搜索树集原版 没有提取到父类
 * @date 2021/3/2 19:23
 */
public class MyBinarySearchTree<E>  implements BinaryTreeInfo {
    private int size;
    private Node<E> root;
    private Comparator<E> comparator;

    public MyBinarySearchTree() {
    }

    public MyBinarySearchTree(Comparator comparator){
        this.comparator = comparator;
    }

    /**
     * 元素数量
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 查看二叉搜索树是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清除所有元素
     */
    public void clear(){
        root = null;
        size = 0;
    }

    /**
     * 添加元素
     * @param element
     */
    public void add(E element){
        elementNotNullCheck(element);

        if (root == null){
            root = new Node<>(element, null);
            size++;
            return;
        }

        Node<E> node = root;
        Node<E> parent = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element, node.element);

            parent = node;

            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {
                node.element = element;
                return;
            }
        }

        if (cmp > 0){
            parent.right = new Node<>(element, parent);
        }else if (cmp < 0){
            parent.left = new Node<>(element, parent);
        }
        size++;
    }

    /**
     * 删除元素
     * @param element
     */
    public void remover(E element){
        remover(node(element));
    }

    private void remover(Node<E> node){
        if (node == null){
            return;
        }

        size--;

        if (node.hasTwoChildren()){//度为2
            Node<E> p = predecessor(node);
            node.element = p.element;
            node = p;
        }

        Node<E> childNode = node.left != null ? node.left : node.right;

        if (childNode != null){//度为1
            childNode.parent = node.parent;
            if (childNode.parent == null){//如果删除的节点父节点是null 说明是根节点
                root = childNode;
            }else if (childNode.parent.left == node){
                childNode.parent.left = childNode;
            }else {
                childNode.parent.right = childNode;
            }
        }else if (node.parent == null){//是叶子节点 又是根节点
            root = null;
        }else {//是叶子节点 度为0
            if (node.parent.left == node){
                node.parent.left = null;
            }else {
                node.parent.right = null;
            }
        }

    }

    /**
     * 通过元素查找节点
     * @param element
     * @return
     */
    private Node<E> node(E element){
        elementNotNullCheck(element);

        if (root == null){
            return null;
        }

        Node<E> node = root;
        while (node != null){
            int cmp = compare(element, node.element);
            if (cmp == 0){
                return node;
            }else if (cmp > 0){
                node = node.right;
            }else {
                node = node.left;
            }
        }

        return null;
    }

    public boolean contains(E element){
        elementNotNullCheck(element);

        if (root == null){
            return false;
        }

        Node<E> node = root;
        int cmp = 0;
        while (node != null){
            cmp = compare(element, node.element);

            if (cmp > 0){
                node = node.right;
            }else if (cmp < 0){
                node = node.left;
            }else {
                return true;
            }
        }

        return false;
    }

    /**
     * 前驱节点
     * @param node
     * @return
     */
    private Node<E> predecessor(Node<E> node){

        if (node == null){
            return null;
        }

        if (node.left != null){
            Node<E> n = node.left;
            while (n.right != null){
                n = n.right;
            }
            return n;
        }
        while (node.parent != null && node == node.parent.left){
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 后继节点
     * @param node
     * @return
     */
    private Node<E> successor(Node<E> node){
        if (node == null){
            return null;
        }
        if (node.right != null){
            Node<E> s = node.right;
            while (s.left != null){
                s = s.left;
            }
            return s;
        }
        while (node.parent != null && node == node.parent.right){
            node = node.parent;
        }

        return node.parent;
    }

    /**
     * 判断是否为完全二叉树
     * @return
     */
    public boolean isComplete(){
        if (root == null){
            return false;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        boolean b = false;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            if (b && !node.isLeaf()){
                return false;
            }
            if (node.left != null){
                queue.offer(node.left);
            }else if (node.right != null){
                return false;
            }
            if (node.right != null){
                queue.offer(node.right);
            }else {
                b = true;
            }
        }
        return true;
    }

    /**
     * 获取树的高度
     * @return
     */
    public int height(){
        if (root == null){
            return 0;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        int count = 1;
        int sum = 0;
        while (!queue.isEmpty()){
            Node<E> node = queue.poll();
            count--;
            if (node.left != null){
                queue.offer(node.left);
            }
            if (node.right != null){
                queue.offer(node.right);
            }

            if (count == 0){
                sum++;
                count = queue.size();
            }
        }
        return sum;
    }

    /**
     * 递归计算高度
     * @return
     */
    public int heightRecursion(){
        return heightRecursion(root);
    }

    private int heightRecursion(Node<E> node){
        if (node == null){
            return 0;
        }
        return 1 + Math.max(heightRecursion(node.left), heightRecursion(node.right));
    }

    public static abstract class Visitor<E>{
        boolean stop;
        abstract boolean visitor(E element);
    }
    /**
     * 比较器
     * @param e1
     * @param e2
     * @return
     */
    private int compare(E e1 , E e2){
        if (comparator != null){
            return comparator.compare(e1, e2);
        }
        return ((Comparable<E>)e1).compareTo(e2);
    }

    /**
     * 前序遍历
     */
    public void preorderTraversal(Visitor<E> visitor){
        preorderTraversal(root,visitor);
    }

    private void preorderTraversal(Node<E> node , Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
        preorderTraversal(node.left,visitor);
        preorderTraversal(node.right,visitor);
    }

    /**
     * 前序遍历迭代
     */
    public void preorder(Visitor<E> visitor){
        if (root == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            visitor.visitor(node.element);
            if (node.right != null){
                deque.push(node.right);
            }
            if (node.left != null){
                deque.push(node.left);
            }
        }
    }
    /**
     * 中序遍历
     */
    public void inorderTraversal(Visitor<E> visitor){
        inorderTraversal(root,visitor);
    }

    private void inorderTraversal(Node<E> node ,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        inorderTraversal(node.left ,visitor);
        if (visitor.stop == true){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
        inorderTraversal(node.right ,visitor);
    }

    /**
     * 中序遍历迭代
     * @param visitor
     */
    public void inorder(Visitor<E> visitor){
        if (root == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            if (node.right != null){
                deque.push(node.right);
            }

            if (node.isLeaf()){
                visitor.visitor(node.element);
            }else {
                deque.push(new Node<>(node.element, null));
            }

            if (node.left != null){
                deque.push(node.left);
            }
        }
    }

    /**
     * 后续遍历
     */
    public void postorderTraversal(Visitor<E> visitor){
        postorderTraversal(root, visitor);
    }

    private void postorderTraversal(Node<E> node ,Visitor<E> visitor){
        if (node == null || visitor.stop){
            return;
        }
        postorderTraversal(node.left ,visitor);
        postorderTraversal(node.right ,visitor);
        if (visitor.stop == true){
            return;
        }
        visitor.stop = visitor.visitor(node.element);
    }

    /**
     * 后续遍历迭代
     * @param visitor
     */
    public void postorder(Visitor<E> visitor){
        if (root == null){
            return;
        }
        Deque<Node<E>> deque = new LinkedList<>();
        deque.push(root);

        while (!deque.isEmpty()){
            Node<E> node = deque.pop();

            if (node.isLeaf()){
                visitor.visitor(node.element);
            }else {
                deque.push(new Node<E>(node.element,null));
            }
            if (node.right != null){
                deque.push(node.right);
            }
            if (node.left != null){
                deque.push(node.left);
            }
        }
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor){
        if (root == null){
            return;
        }
        levelOrderTraversal(root, visitor);
    }

    private void levelOrderTraversal(Node<E> node ,Visitor<E> visitor){
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            Node<E> poll = queue.poll();
            if(visitor.visitor(poll.element)){
                return;
            };
            if (poll.left != null){
                queue.offer(poll.left);
            }
            if (poll.right != null){
                queue.offer(poll.right);
            }
        }
    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        toString(root, sb ,"");
        return sb.toString();
    }

    private void toString(Node<E> node,StringBuffer sb , String prefix){
        if (node == null){
            return;
        }
        toString(node.left,sb,prefix +"【L】");
        sb.append(prefix).append("【").append(node.element).append("】\n");
        toString(node.right, sb,prefix +"【R】");
    }

    /**
     * 判断元素是否为空
     * @param element
     */
    private void elementNotNullCheck(E element){
        if (element == null){
            throw new IllegalArgumentException("element must not be null!");
        }
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>)node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>)node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>)node).element;
    }

    private static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element , Node<E> parent){
            this.element = element;
            this.parent = parent;
        }

        /**
         * 判断是否为叶子节点
         * @return
         */
        public boolean isLeaf(){
            return left == null && right == null;
        }

        /**
         * 判断是否有两个子节点
         * @return
         */
        public boolean hasTwoChildren(){
            return left != null && right != null;
        }
    }

}
